﻿// ------------------------------------------------------------------------------------------------
//  <copyright file="HashLinkTable.cs" company="Iveely">
//    Copyright (c) Iveely Liu.  All rights reserved.
//  </copyright>
//  
//  <Create Time>
//    03/02/2013 21:59 
//  </Create Time>
//  
//  <contact owner>
//    liufanping@iveely.com 
//  </contact owner>
//  -----------------------------------------------------------------------------------------------

#region

using System;
using System.Collections;

#endregion

namespace IveelySE.NLP.Common.DataStructure.Table
{
    /// <summary>
    ///   哈希链表
    /// </summary>
    [Serializable]
    public class HashLinkTable
    {
        /// <summary>
        ///   默认表的容量(不能无限制，太大会占用过多内存影响性能)
        /// </summary>
        private const int Size = 3;

        /// <summary>
        ///   Hashtable 是我们最基础的结构
        ///   存储结构如下：
        ///   Key-value（content,next）
        /// </summary>
        private readonly Hashtable _table;

        /// <summary>
        ///   头部节点
        /// </summary>
        private NodeValue _head;

        /// <summary>
        ///   尾部节点
        /// </summary>
        private NodeValue _tail;

        /// <summary>
        ///   构造方法
        /// </summary>
        public HashLinkTable()
        {
            //实例化头部节点
            this._head = new NodeValue();
            //实例化尾部节点
            this._tail = new NodeValue();
            //实例化Hash表
            this._table = new Hashtable();
        }

        /// <summary>
        ///   添加节点
        /// </summary>
        /// <param name="key"> 关键字 </param>
        /// <param name="values"> 值 </param>
        public void Add(object key, object values)
        {
            //如果不包含此关键字，则直接添加到头部
            if(this.ContainsKey(key))
            {
                //找到在此关键字
                var nodeValue = (NodeValue) this._table[key];
                //将关键字的前驱结点的后继结点该向它的后继节点
                if(nodeValue.Next == null)
                {
                    ((NodeValue) this._table[nodeValue.Pre.Key]).Next = null;
                    //尾节点等于它的前驱结点
                    this._tail = (NodeValue) this._table[nodeValue.Pre.Key];
                }
                else
                {
                    ((NodeValue) this._table[nodeValue.Pre.Key]).Next = (NodeValue) this._table[nodeValue.Next.Key];
                }
                //将关键字的后继节点的前驱指针指向它的前驱结点
                if(nodeValue.Next != null)
                {
                    ((NodeValue) this._table[nodeValue.Next.Key]).Pre = (NodeValue) this._table[nodeValue.Pre.Key];
                }
                //删除它在表中的存在
                this._table.Remove(key);
            }
            //添加入节点
            this.AddNode(key, values);
        }

        /// <summary>
        ///   返回缓存中存在的值
        /// </summary>
        /// <param name="key"> 查找的关键字 </param>
        /// <returns> 返回关键字对应的结果 </returns>
        public object FindValue(object key)
        {
            return this.ContainsKey(key) ? ((NodeValue) this._table[key]).Content : "NULL";
        }

        /// <summary>
        ///   清楚搜索缓存
        /// </summary>
        public void Clean()
        {
            this._table.Clear();
            this._head = new NodeValue();
        }


        /// <summary>
        ///   是否包含关键字
        /// </summary>
        /// <param name="key"> 用户的关键字 </param>
        /// <returns> True为存在，False为不存在 </returns>
        private bool ContainsKey(object key)
        {
            return this._table.ContainsKey(key);
        }


        /// <summary>
        ///   添加节点到表头
        /// </summary>
        /// <param name="key"> 节点的Key </param>
        /// <param name="values"> 节点的Value </param>
        private void AddNode(object key, object values)
        {
            //新建节点
            var nodeValue = new NodeValue
                                {
                                    Content = values,
                                    Next = this._head.Next,
                                    Pre = null,
                                    Key = key
                                };
            //Head的子节点的前驱结点指向nodeValue
            if(this._head.Next != null)
            {
                this._head.Next.Pre = nodeValue;
                nodeValue.Next = this._head.Next;
            }
                //那么此节点是默认的尾节点
            else
            {
                this._tail = nodeValue;
            }
            ////当前节点为Head节点
            //Head = nodeValue;
            //head的后驱节点时nodeValue
            this._head.Next = nodeValue;
            this._head.Pre = null;
            //nodeValue的前驱结点指向Head
            nodeValue.Pre = this._head;
            //当前节点为Head节点
            //Head = nodeValue;
            //Hash表中先加入
            this._table.Add(key, nodeValue);
            //如果大于了表的容量
            if(this._table.Count > Size)
            {
                //删除最近进入的元素
                NodeValue preValue = this._tail.Pre;
                this._table.Remove(this._tail.Key);
                this._tail = preValue;
                this._tail.Next = null;
            }
        }

        #region Nested type: NodeValue

        /// <summary>
        ///   内部类，节点值
        /// </summary>
        public class NodeValue
        {
            /// <summary>
            ///   前驱指针
            /// </summary>
            public NodeValue Pre { get; set; }

            /// <summary>
            ///   节点关键字
            /// </summary>
            public object Key { get; set; }

            /// <summary>
            ///   节点值
            /// </summary>
            public object Content { get; set; }

            /// <summary>
            ///   节点的下一节点值
            /// </summary>
            public NodeValue Next { get; set; }
        }

        #endregion
    }
}